package com.leecode.xiehf.page_01;

/**
 *
 */
public class Solution_0010 {

    public static void main(String[] args) {
        Solution_0010 solution_0010 = new Solution_0010();
        boolean result = solution_0010.isMatch("aaa", "*b");
        System.out.println(result);
    }

    /**
     * size  0    1    2     3     4 ...  (p)
     * 0    true      true        true
     * 1
     * 2
     * 3
     * 4
     * .
     * .
     * .
     * (s)
     */
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        // 动态规划初始参照
        dp[0][0] = true;
        for (int j = 2; j <= n; j += 2) {
            // 偶数位 为* 可以匹配0个 所以也是true
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
        // i j 都是要理解为 dp的下标  dp左上角是初始化的true
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char ss = s.charAt(i - 1);
                char pp = p.charAt(j - 1);
                if (ss == pp || pp == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pp == '*') {
                    // 因为题目说明了一定是有效的p和s，所以不会出现*开头的p，这里不要考虑越界问题
                    if (dp[i][j - 2]) {
                        // 任意行
                        dp[i][j] = true;
                    } else if (p.charAt(j - 2) == ss || p.charAt(j - 2) == '.') {
                        // 1. p[j-1] = * 的情况下 p[j-2]=s[i-1] 也就是s是连续2个相同字符
                        // 2. p[j-1] = * 的情况下 p[j-2]='.' 也就是不管s是什么字符都是算匹配的
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
}
